package week_01;

import java.util.*;

public class Class1 {
    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    public boolean hasCycle_141_1(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return false;
        }
        ListNode fast = head.next.next;
        ListNode slow = head.next;
        while (slow != fast) {
            if (fast == null || fast.next == null || fast.next.next == null) {
                return false;
            }
            fast = fast.next.next;
            slow = slow.next;
        }
        return true;
    }

    public boolean hasCycle_141_2(ListNode head) {
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            head = head.next;
            if (head == fast) {
                return true;
            }
        }
        return false;
    }

    public ListNode detectCycle_142_1(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        ListNode fast = head.next.next;
        ListNode slow = head.next;
        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return null;
            }
            fast = fast.next.next;
            slow = slow.next;
        }

        fast = head;
        while (slow != fast) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

    public ListNode detectCycle_142_2(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                while (slow != head) {
                    head = head.next;
                    slow = slow.next;
                }
                return head;
            }
        }
        return null;
    }

    public static boolean isValid_20_1(String s) {
        //给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
        // 思路：左括号入栈，右括号pop()比对是不是对
        // 细节：括号字符比对。需要switch三种括号
        char[] chars = s.toCharArray();
        Stack<String> stack = new Stack<>();
        try {
            for (int i = 0; i < chars.length; i++) {
                String str = String.valueOf(chars[i]);

                if (str.equals("(") || str.equals("{") || str.equals("[")) {
                    stack.push(str);
                } else if (str.equals(")") && !stack.pop().equals("(")) {
                    return false;
                } else if (str.equals("}") && !stack.pop().equals("{")) {
                    return false;

                } else if (str.equals("]") && !stack.pop().equals("[")) {
                    return false;
                }
            }
            return stack.empty();
        } catch (Exception e) {
            return false;
        }
    }


    public static boolean isValid_20_2(String s) {
        int n = s.length();
        if (n % 2 == 1) {
            return false;
        }
        Map<Character, Character> characterMap = new HashMap<Character, Character>() {{
            put(']', '[');
            put(')', '(');
            put('}', '{');
        }};
        Deque<Character> statck = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (characterMap.containsKey(c)) {
                if (statck.isEmpty() || !statck.peek().equals(characterMap.get(c))) {
                    return false;
                }
                statck.pop();
            } else {
                statck.push(c);
            }
        }
        return statck.isEmpty();
    }

    public int calculate_224(String s) {
        // 中缀 "(1+(4+5+2)-3)+(6+8)" -> 转后缀
        List<String> tokens = new ArrayList<>();
        Deque<Character> ops = new LinkedList<>();
        boolean num_start = false;
        boolean need_zero = true;
        int val = 0;
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch >= '0' && ch <= '9') {
                val = val * 10 + ch - '0';
                num_start = true;
                continue;
            } else if (num_start) {
                tokens.add(String.valueOf(val));
                num_start = false;
                need_zero = false;
                val = 0;
            }
            if (ch == ' ') {
                continue;
            }
            if (ch == '(') {
                ops.push(ch);
                need_zero = true;
                continue;
            } else if (ch == ')') {
                // '(' ')' 不入栈
                while (ops.peek() != '(') {
                    tokens.add(String.valueOf(ops.pop()));
                }
                ops.pop();
                need_zero = false;
                continue;
            }
            // 处理+-*/
            if (need_zero) {
                tokens.add(String.valueOf(0));
            }

            while (!ops.isEmpty() && getRandk(ops.peek()) >= getRandk(ch)) {
                tokens.add(String.valueOf(ops.pop()));
            }

            ops.push(ch);
            need_zero = true;
        }
        // 如果还有数据
        if (num_start) {
            tokens.add(String.valueOf(val));
        }
        while (!ops.isEmpty()) {
            tokens.add(String.valueOf(ops.pop()));
        }
        return evalRPN_150(tokens.toArray(new String[tokens.size()]));

    }

    public int getRandk(char c) {
        if (c == '+' || c == '-'){
            return 1;
        }
        if (c == '*' || c == '/'){
            return 2;
        }
        return 0;
    }

    public int evalRPN_150(String[] tokens) {
        // 计算后缀表达式：tokens = ["2","1","+","3","*"]
        Deque<Integer> calStack = new LinkedList<>();
        for (int i = 0; i < tokens.length; i++) {
            String s = tokens[i];
            if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) {
                int n1 = calStack.pop();
                int n2 = calStack.pop();
                calStack.push(clac(n2, n1, s));
            } else {
                calStack.push(Integer.parseInt(s));
            }
        }
        return calStack.pop();
    }

    public int clac(int a, int b, String op) {
        if (op.equals("+")) {
            return a + b;
        }
        if (op.equals("-")){
            return a - b;
        }
        if (op.equals("*")){
            return a * b;
        }
        if (op.equals("/")){
            return a / b;
        }
        return 0;
    }

    public boolean isNumber(String s) {
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) < '0' || s.charAt(i) > '9') {
                return false;
            }
        }
        return true;
    }

    public ListNode mergeTwoLists_21(ListNode l1, ListNode l2) {
        ListNode protect =new ListNode(-1);
        ListNode pre =protect;
        while(l1!=null && l2!=null){
            if(l1.val<=l2.val){
                pre.next=l1;
                l1=l1.next;
            }else{
                pre.next=l2;
                l2=l2.next;
            }
            pre=pre.next;
        }
        if(l1!=null){
            pre.next=l1;
        }else{
            pre.next=l2;
        }
        return protect.next;

    }

    public int[] plusOne_66(int[] digits) {
        int n=digits.length;
        boolean plusOne=true;
        for(int i =n-1;i>=0;i--){
            if(plusOne) {
                if(digits[i]+1>9){
                    digits[i]=(digits[i]+1)%10;
                    plusOne=true;
                } else{
                    digits[i]=digits[i]+1;
                    plusOne=false;
                }
            }
        }
        if(plusOne) {
            int[] res =new int[n+1];
            res[0]=1;
            for(int i=1;i<res.length;i++){
                res[i]=digits[i-1];
            }
            return res;
        }else{
            return digits;
        }
    }

    public static void main(String[] args) {
        String s = "()[]{}";
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            char str = chars[i];
            System.out.println(str);

        }
        System.out.println(isValid_20_1(s));

        String s2 = "1-(+1+1)";
        Class1 class1 = new Class1();
        System.out.println(class1.calculate_224(s2));

        int[] t1=new int[]{9};
        System.out.println(class1.plusOne_66(t1));
    }
}
